package 滑动窗口And双指针.双指针.快慢指针;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/2 15:36
 */
public class leetcode287寻找重复数 {

    /*
      要求 ： 时间复杂度 O（N）（线性时间复杂度）
      空间复杂度 O（1）

      快慢指针：
     */

    public int solution(int nums[]){
        int slow = 0, fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast){
                slow = 0;
                while(slow != fast){
                    slow = nums[slow];
                    fast = nums[fast];
                }
                // 注意 这个 break 的位置 不要 放错了!
                break;
            }
        }
        return slow;
    }



    /*
     原地 哈希的 写法
    O(N) O(1)
     */
    public int solutionHash(int nums[]){
        for(int i = 0;i < nums.length;i++){
            while(nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]){
                swap(nums,i,nums[i] - 1);
            }
        }
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != i + 1){
                return nums[i];
            }
        }
        return 0;
    }

    private void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }




    /*
      时间复杂度 O（N * logN）
      空间复杂度 O（1）
     */

    public int solutionSort(int nums[]){
        Arrays.sort(nums);
        for(int i = 0;i <nums.length - 1;i++){
            if(nums[i] == nums[i + 1]){
                return nums[i];
            }
        }
        return -1;
    }


    /*
      暴力做法
      时间 空间 都是 O（N）
     */
    public int findDuplicate(int[] nums) {
        int [] map = new int [nums.length + 2];
        for(int num : nums){
            // 这样写 ， 不就更优雅！
            if(map[num] > 0){
                return num;
            }
            map[num] ++;
        }
        return  -1;
    }

}
